// https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

// 题干： 输⼊⼀个递增排序的数组和⼀个数字 s ，在数组中查找两个数，使得它们的和正好是 s 。如果有多
//        对数字的和等于 s ，则输出任意⼀对即可。

// 示例：输⼊： nums = [2,7,11,15], target = 9
//       输出： [2,7] 或者 [7,2]

// 碎语：利用好递增的特性，申请两个对撞指针
//       如果和大于s，那么[left,right)都不可能成为答案，right左移
//       如果和小于s，那么(left,right]都不可能成为答案，left右移

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int s)
    {
        int left = 0, right = nums.size() - 1;

        while (left != right){
            if (nums[left] + nums[right] > s) right--;
            else if (nums[left] + nums[right] < s) left++;
            else return {nums[left], nums[right]};
        }

        return {};
    }
};

int main()
{
    Solution sol;
    int s = 9;
    vector<int> nums = {2,7,11,15};

    vector<int> index = sol.twoSum(nums, s);
    for (auto num : index){
        cout << num << " ";
    }
    cout << endl;

    return 0;
}